The present invention includes an algorithm that produces upper bounds (and feasible solutions) and lower bounds for the so-called Prize-Collecting Steiner Tree Problem in Graphs (PCSPG). The term “graphs” as used herein, means graphic portrayals that may represent edges, vertices and other aspects of undirected networks, and arcs, vertices and other aspects of directed networks. The algorithm is a heuristic or modeling tool that in computational experiments was shown to find better-quality solutions than other algorithms published in the literature.
Network planning and design is a very resource intensive process; i.e., time, effort and capital resources, undertaken by network service providers to assure that new or additional network capacity and services will meet performance, reliability and cost targets. Costs to be considered may include system as well as hardware/software design, development, installation, operation, replacement, maintenance and retirement costs. Benefits to be considered may include revenue from improvement to current services as well as possible new services or complementary services, and reduced ongoing costs such as operations, replacement, maintenance and retirement costs.
A key part of the planning process is where to place fiber optic cable when developing and deploying a fiber optic network. In this optimization problem, inputs are typically a graph or map representing a city street, where one vertex is a root vertex while other vertices are customer premises or street corners, and edges are potential locations where fiber optical cables can be placed. Each customer premises has associated with it potential revenue that could be gained if a path from the root vertex to the premises is built with fiber optical cables. Each edge has associated with it a cost to place fiber optical cable connecting the edge's endpoints. The goal of a network optimization problem is to place fiber optical cables such that the difference between the total revenue and the total cost of the fiber optical cables is maximized.
The Prize-Collecting Steiner Tree Problem in Graphs (PCSPG) is a mathematical problem wherein model edge costs and vertex profits yield a subtree optimization, in this case lowest cost. This is accomplished by minimizing the sum of the total cost of all edges in the subtree plus the total profit of all vertices not contained in the subtree.
It would be desirable to provide methods to improve the modeling and design of networks utilizing an algorithm for the PCSPG, such as utility networks (i.e. fiber optics or energy distribution) where profit generating customers and the network connecting them have to be chosen in a cost effective manner.